Quiz (Week 2)

1 Types and Constructors

Consider the following type definitions.

type B = Bool
data X = A X
       | B B
       | C Y
data Y = Y B

1.1 Question 1

Which of the following identifiers can stand for types in the above definitions? Check all that apply.

✗A
✔B
✗C
✔X
✔Y

The three types defined are B, X, and Y. C :: Y -> X is a constructor of the type X, but not a type.

1.2 Question 2

Which of the following identifiers can stand for constructors in the above definitions? Check all that apply.

✔A
✔B
✔C
✗X
✔Y

The type X introduces three constructors, A, B and C, and the type Y defines a constructor, also called Y.

2 Types in Design

For each of the following use cases, choose the type definitions that best reflect this use case, eliminating as many possible errors or invalid values as possible.

2.1 Question 3

A connection is in one of three states: connected, connecting or disconnected. It also contains the following information:

The destination IP address

If it is in the disconnected state, the time it disconnected.

If it is in the connected state, the arrival time of the most recent packet, if one exists.

If it is in the connected state, the size of the most recent packet, if one exists.

If it is in the connecting state, the time the connection was initiated.

✗

data State = Connected | Connecting | Disconnected

data Connection
  = Connection
      IPAddress      -- destination
      State
      (Maybe Time)   -- time when disconnected
      (Maybe Time)   -- time when initiated
      (Maybe Time)   -- arrival of most recent packet
      (Maybe Size)   -- size of most recent packet

✗

data State
  = Connected (Maybe Time) (Maybe Size)  -- packet time, size
  | Connecting  Time                     -- time when initiated
  | Disconnected Time                    -- time when disconnected

data Connection
   = Connection 
       IPAddress     -- destination
       State

✗

data State = Connected | Connecting | Disconnected

data Connection
  = Connection
      IPAddress             -- destination
      State
      (Maybe Time)          -- time when disconnected
      (Maybe Time)          -- time when initiated
      (Maybe (Time, Size))  -- info of most recent packet

✔

data State
  = Connected (Maybe (Time,Size))       -- info of most recent packet
  | Connecting Time                     -- time when initiated
  | Disconnected Time                   -- time when disconnected

data Connection
   = Connection 
       IPAddress     -- destination
       State

The first answer is very unstructured, as it does not enforce the relationship between the state the connection is in and the data that should be present in the connection. For example, this means that it's possible to have a connection in the disconnected state, but without a timestamp for time when disconnected. It also allows a packet arrival time to be present without a size, which is not possible.

The second answer does enforce the relationship between data and state, but does not fix the problem with the packet size and time.

The third answer does fix the problem with the packet size and time, but does not fix the relationship between data and state.

The fourth answer is therefore correct.

2.2 Question 4

A message is encrypted using a password. The system will not allow messages to be encrypted with weak passwords. Messages can only be logged if encrypted.

✗

checkStrength :: String -> Bool
encrypt       :: String -> String -> String
log           :: String -> Log -> Log

✗

data Encrypted = E String
checkStrength :: String -> Bool
encrypt       :: String -> String -> Encrypted
log           :: Encrypted -> Log -> Log

✔

data Password  = P String
data Encrypted = E String
checkStrength :: String -> Maybe Password
encrypt       :: String -> Password -> Encrypted
log           :: Encrypted -> Log -> Log

✗

data Password  = P String
checkStrength :: String -> Maybe Password
encrypt       :: String -> Password -> String
log           :: String -> Log -> Log

There are three requirements:

We must prevent the password and message parameters to encrypt from being swapped.
We must not allow an unchecked password to be used for encryption.
We must not allow unencrypted messages to be logged.

The first answer doesn't meet any requirements. The second meets the third requirement only. The third is correct. The last one meets only the first and second requirements.

Notice that the third answer embodies the parse, don't validate principle: the validation function checkStrength parses the String into a more structured data type Password. The encrypt function does not validate that its second argument has the correct strength: instead, it consumes a data type Password that cannot represent the illegal state (non-strong password) by design.

3 Monoids and Semigroups

3.1 Question 5

Which of the following instance Semigroup where declarations create lawful instances (i.e. ones that satisfy the associativity requirement)?

✔

data X = X Bool
instance Semigroup X where
  X a <> X b = X (a || b)

✗

data X = X Bool
instance Semigroup X where
  X a <> X b = X (not a || b)

✔

data X = X Bool
instance Semigroup X where
  X a <> X b = X (a `xor` b)
    where xor True  x = not x
          xor False x = x

✔

data X = X Bool
instance Semigroup X where
  X a <> X b = X a

The only operation that does not satisfy the associative law is the second one (implication).

3.2 Question 6

Which of the following would constitute valid monoid instances?

✗The type Int, the max function and identity element 0
✔The type Bool, the (||) function and identity element False
✗The type Bool, the (||) function and identity element True
✗The type Int, the function (\a b -> (a + b) `div` 2), and identity element 0.

The first answer is not a monoid because 0 is not an identity element for max. For example max (-1) 0 == 0.

The second answer is a monoid because False is the identity element for disjunction (||), i.e. x || False == x and False || x == x both hold for all x :: Bool.

The third answer is not a monoid because True is not an identity element for (||), as x || True == True for all x.

The last is not a monoid (and not even a semigroup) because the given average function is not associative.

4 Relations

4.1 Question 7

Check all of the following that are valid total orders on the type Int.

✔(<=)
✗\x y -> x `mod` y == 0
✔(>=)
✗(/=)

Both <= and >= are total order relations, since they satisfy reflexivity, transitivity, antisymmetry and totality. Divisibility (2) is a partial order, but not a total order: 2 does not divide 3 and 3 does not divide 2 either. Moreover, divisibility as defined above is a partial function: it would raise an error when called with 0 as its second argument. Non-equality is not reflexive, and so not a total order.

4.2 Question 8

Check all of the following that are valid equivalence relations on the type Int.

✔(==)
✔\x y -> x `mod` 10 == y `mod` 10
✗(>=)
✗(/=)

Equality is an equivalence relation, as is congruence mod 10. That is because they satisfy reflexivity, transitivity and symmetry. The ordering >= is not symmetric, while /= is not reflexive or transitive either.

Submission is already closed for this quiz. You can click here to check your submission (if any).